home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / k_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.1 KB  |  103 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  k_heap.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_KHEAP_H
  17. #define LEDA_KHEAP_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // k-nary Heaps
  21. //------------------------------------------------------------------------------
  22.  
  23.  
  24. #include <LEDA/basic.h>
  25.  
  26. class k_heap_elem
  27. {
  28.   friend class k_heap;
  29.  
  30.   GenPtr key;
  31.   GenPtr inf;
  32.  
  33.   int index;
  34.  
  35.   k_heap_elem(GenPtr k, GenPtr i, int pos) { key = k; inf = i; index = pos; }
  36.  
  37.   LEDA_MEMORY(k_heap_elem)
  38.  
  39. };
  40.  
  41.  
  42. typedef k_heap_elem* k_heap_item;
  43.  
  44.  
  45. class k_heap  {
  46.  
  47. virtual int  cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  48. virtual void copy_key(GenPtr&)   const {}
  49. virtual void copy_inf(GenPtr&)   const {}
  50. virtual void clear_key(GenPtr&)  const {}
  51. virtual void clear_inf(GenPtr&)  const {}
  52. virtual void print_key(GenPtr x) const { Print(x); }
  53. virtual void print_inf(GenPtr x) const { Print(x); }
  54.  
  55. virtual int  int_type() const { return 0; }
  56.  
  57.  
  58. int          K;
  59. int          count;
  60. int          max_size;
  61. k_heap_item* HEAP;
  62.  
  63. void rise(int,k_heap_item);
  64. void sink(int,k_heap_item);
  65.  
  66. void check(k_heap_item);
  67.  
  68. protected:
  69.  
  70. k_heap_item item(GenPtr p) const { return k_heap_item(p); }
  71.  
  72. public:
  73.  
  74. k_heap_item insert(GenPtr, GenPtr);
  75. k_heap_item find_min()  const      { return HEAP[1];  }
  76. k_heap_item first_item() const     { return HEAP[1]; }
  77. k_heap_item next_item(k_heap_item it) const { return HEAP[it->index+1];}
  78.  
  79. void decrease_key(k_heap_item, GenPtr);
  80. void change_inf(k_heap_item, GenPtr);
  81. void del_item(k_heap_item);
  82. void del_min() { del_item(find_min()); }
  83.  
  84. GenPtr key(k_heap_item it) const { return it->key; }
  85. GenPtr inf(k_heap_item it) const { return it->inf; }
  86.  
  87. int  size()    const  { return count;    }
  88. bool empty()   const  { return count==0; }
  89.  
  90. void clear();
  91. void print();
  92.  
  93. k_heap& operator=(const k_heap&);
  94.  
  95. k_heap(int n=0,int k=2);  // default: binary heap
  96. k_heap(const k_heap&);
  97.  
  98. virtual ~k_heap();
  99.  
  100. };
  101.  
  102. #endif
  103.